package com.jiang.专题.动态规划.Q91;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/06 17:08
 */
class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        char[] arr = s.toCharArray();
        int[] dp = new int[len + 1]; // dp[i] 表示从第i个字符及其之前有几种解码方式
        if (arr[0] == '0') {
            return 0;
        } else {
            dp[0] = 1;
            dp[1] = 1;
        }
        for (int i = 1; i < len; i++) {
            int pre = (arr[i - 1] - '0') * 10;
            int now = arr[i] - '0';
            int add = pre + now;
            if (now != 0) {
                if (pre > 0 && add <= 26)
                    dp[i + 1] = dp[i] + dp[i - 1]; // 例如122|1 + 12|21，122的三种解码 方式+ 12的两种解码方式
                else
                    dp[i + 1] = dp[i]; // 例如 122 | 8 只有122的三种解码方式
            } else {
                if (add == 0 || add > 20)
                    return 0; // 例如 10|0 13|0
                else
                    dp[i + 1] = dp[i - 1]; // 例如 12|20 只有 12的两种解码方式
            }
        }
        return dp[len];
    }
}
